package com.itheima.leetcode.od.c.recursion;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * <h3>快速人名查找</h3>
 */
public class QuickNameSearch {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        String input = scanner.nextLine();
        String exp = scanner.nextLine();

        // 使用逗号分割名字列表
        String[] names = input.split(",");
        List<String> ansList = new ArrayList<>();

        for (String name : names) {
            // 使用空格分割每个人的名字
            // trim() 用于去除可能存在的前后空格
            String[] person = name.trim().split("\\s+");

            // 检查 person 数组是否为空，防止输入是 "" 或 " , " 这种情况
            if (person.length > 0 && !person[0].isEmpty()) {
                if (dfs(person, 0, exp, 0)) {
                    ansList.add(name);
                }
            }
        }

        // 使用 String.join 高效地拼接结果
        System.out.println(String.join(",", ansList));
        scanner.close();
    }

    /**
     * 深度优先搜索，用于匹配。
     *
     * @param person 名字被空格分割后的单词数组
     * @param pi     当前正在匹配 person 数组中的第 pi 个单词
     * @param exp    目标匹配表达式
     * @param ej     当前正在匹配 exp 字符串的第 ej 个字符
     * @return 如果匹配成功，返回 true
     */
    private static boolean dfs(String[] person, int pi, String exp, int ej) {
        // 有任意一方已经使用完了
        if (pi == person.length || ej == exp.length()) {
            // 只有两方同时使用完了，才是ok的
            return (pi == person.length && ej == exp.length());
        }

        String name = person[pi];
        // 首字母不匹配，直接退出
        if (name.charAt(0) != exp.charAt(ej)) {
            return false;
        }

        // 尝试让 name 消耗 exp 的多个字符
        int cnt = 1;
        // 当 name 和 exp 的后续字符能继续匹配时
        while (cnt < name.length() && ej + cnt < exp.length() && name.charAt(cnt) == exp.charAt(ej + cnt)) {
            // 尝试从这个匹配点进行下一步的 dfs
            if (dfs(person, pi + 1, exp, ej + cnt + 1)) {
                return true; // 如果后续匹配成功，直接返回 true
            }
            cnt++;
        }

        // 首字母匹配，name 只消耗 exp 的一个字符，然后进行下一个单词的匹配
        return dfs(person, pi + 1, exp, ej + 1);
    }
}